/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author zhong
 *
 */
public class LongestArithmeticSequence {
	public int longestArithSeqLength(int[] A) {
		Map<Integer, Map<Integer, List<int[]>>> map = new HashMap<>();
		for (int i = 0; i < A.length; i++) {
			for (int j = i + 1; j < A.length; j++) {
				int diff = A[j] - A[i];
				if (map.containsKey(diff)) {
					Map<Integer, List<int[]>> list = map.get(diff);
					boolean added = false;
					List<int[]> list2 = null;
					if (list.containsKey(i)) {
						list2 = list.get(i);
						list2.add(new int[] { i, j });
						list.remove(i);

					} else {
						list2 = new ArrayList<>();
						list2.add(new int[] { i, j });
					}
					if (list.containsKey(j)) {
						List<int[]> old = list.get(j);
						if (old.size() < list2.size()) {
							list.put(j, list2);
						}
					} else {
						list.put(j, list2);
					}
				} else {
					List<int[]> list = new ArrayList<>();
					list.add(new int[] { i, j });
					Map<Integer, List<int[]>> list2 = new HashMap();
					list2.put(diff, list);
					map.put(diff, list2);
				}
			}
		}
		int max = 0;
		for (Map<Integer, List<int[]>> list : map.values()) {
			for (List<int[]> list2 : list.values()) {
				max = Math.max(max, list2.size());
			}
		}
		return max + 1;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] A = { 22, 8, 57, 41, 36, 46, 42, 28, 42, 14, 9, 43, 27, 51, 0, 0, 38, 50, 31, 60, 29, 31, 20, 23, 37, 53,
				27, 1, 47, 42, 28, 31, 10, 35, 39, 12, 15, 6, 35, 31, 45, 21, 30, 19, 5, 5, 4, 18, 38, 51, 10, 7, 20,
				38, 28, 53, 15, 55, 60, 56, 43, 48, 34, 53, 54, 55, 14, 9, 56, 52 };

		System.out.println(new LongestArithmeticSequence().longestArithSeqLength(A));
	}

}
